package me.renyaoxiang.algorithm.sortforstats;


import me.renyaoxiang.algorithm.sort.ArrayUtils;

public class QuickSortForStats {
    public static void sort(StatsContext statsContext, int[] data) {
        sortPart(statsContext, data, 0, data.length - 1);
    }

    public static void sortPart(StatsContext statsContext, int[] data, int start, int end) {
        statsContext.callIndexCompare();
        if (end > start) {

            statsContext.callIndexSign();
            int mid = partition(statsContext, data, start, end);

            statsContext.callIndexSign();
            sortPart(statsContext, data, start, mid - 1);

            statsContext.callIndexSign();
            sortPart(statsContext, data, mid + 1, end);
        }
    }

    public static int partition(StatsContext statsContext, int[] data, int leftIndex, int rightIndex) {
        statsContext.callIndexSign();
        int pivot = leftIndex;

        statsContext.callIndexSign();
        int lowerIndex = leftIndex + 1;

        statsContext.callIndexSign();
        for (int i = lowerIndex; i <= rightIndex; i++) {
            statsContext.callIndexSign();
            statsContext.callIndexCompare();

            statsContext.callCompare();
            if (data[i] < data[pivot]) {

                statsContext.callSwap();
                ArrayUtils.swap(data, lowerIndex, i);

                statsContext.callIndexSign();
                lowerIndex++;
            }
        }
        statsContext.callSwap();
        ArrayUtils.swap(data, pivot, lowerIndex - 1);

        statsContext.callIndexSign();
        return lowerIndex - 1;
    }
}
